#include "vector"

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> vals;
        if(root == NULL) {
            return vals;
        }

        vector<TreeNode*> nodes;

        //首先将root压栈
        nodes.push_back(root);

        while(!nodes.empty()) {
            TreeNode* n = nodes.back();
            vals.push_back(n->val);

            //访问了该节点，出栈
            nodes.pop_back();

            //如果有右子树，压栈保存
            if(n->right) {
                nodes.push_back(n->right);
            }

            //如果有左子树，压栈保存
            if(n->left) {
                nodes.push_back(n->left);
            }
        }

        return vals;
    }
};
